Executing analytical queries on large amounts of data (colloquially known as “big data”) poses a great challenge for database management systems (DBMS). Conventional methods generally require data for analytical queries to be loaded into operational memory from persistent memory to be processed. With data for a single query execution reaching large scales of terra bytes, the operational memory may not be able to hold the full data set required for the query execution. In such a scenario the spill over data may extend into slower memory that has higher storage capacity but much slower input/output (I/O) speed. In addition to slower I/O, more complex operations such as a sort or aggregation performed on big data may further exacerbate the draw on the computational resources of the DBMS. Particularly, comparing and re-arranging terra bytes of data spread across slower memory would substantially decrease the performance of the query and affect the user experience.
The challenge is particularly evident with top-N analytical queries. The term “top-N” query refers to analytical queries that select and sort a data set from a DBMS and output only the first N (top-N) number of rows of the sorted data as the result. The DBMS conventionally loads the target data set of a top-N query into a buffer, sorts the buffer according to the column and order specified in the top-N query, and selects the top-N rows.
When the top-N query is executed on a table with big data, all rows from the big data table may be loaded into a buffer. The buffer, which at that point may span over multiple types of memory and may include slower memories like disk memory, may contain millions of rows that have to be sorted. Sorting so many rows consumes enormous amounts of resources of the DBMS and causes over utilization of computational resources, while the use of slower memory in its turn introduces substantial latency in the processing.
To handle the challenge, new functionalities have been developed for computer hardware to process big data. For example, today's computing nodes usually utilize multiple multi-core processors, in which each multi-core processor consists of multiple independent processing units to execute instructions in parallel manner. However, the multi-core architecture requires new techniques to fully leverage the inherent parallelism in the hardware.
Furthermore, modern computer architecture includes multiple types of memory having different speed and storage capacity, with higher speed memory having lower storage capacity. For example, data operations on cache memory are magnitudes faster than the data operations on disk memory, while the capacity of the disk memory is generally many magnitudes more than the cache memory. Therefore, it is critical for the new techniques to ensure that the data operations are performed on a smaller data that can fit into higher speed lower storage capacity memory.
The approaches described in this section are approaches that could be pursued, but not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section.